//
// Created by LiuYou on 2021/12/1.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>


static int randomNumberFromTheRange(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}


/*
 * 划分, 每一次执行完这个函数就会有一批等于划分值的区域产生。
 *
 * 默认使用 arr[right] 作为划分值, 而 arr[right] 的这个值是随机选出来的。
 *
 * 这个函数就是将数组划分为 < 划分值的部分, = 划分值的部分, > 划分值的部分。3 个部分。
 * 荷兰国旗问题。
 */
/**
 * @brief 这个函数就是将数组划分为 < 划分值的部分, = 划分值的部分, > 划分值的部分。3 个部分。
 */
static std::vector<int> partition(std::vector<int>& arr, int left, int right) {
    // < 区的右边界的索引下标位置。
    // 用 less 这个变量, 记录 < 区域的右边界。
    int less = left - 1;
    // > 区域的左边界的下标位置。
    // 用 more 这个变量, 记录 > 区域的左边界。
    // todo 笔记: 注意: 这里一定一定一定不能 + 1。
    int more = right /*+ 1*/;
    // pivot为划分值。
    int pivot = arr[right];


    while (left < more) {
        /*
         * 如果当前位置的元素值 < 划分值,
         * 那么当前位置的元素和 < 区域的下一个元素交换,
         * 然后 < 区域右扩, left 加 1。
         */
        if (arr[left] < pivot) {
            std::swap( arr[++less], arr[left++] );
        }
            /*
             * 如果当前位置的元素值 > 划分值,
             * 那么把当前位置和元素和 > 区域的前一个元素交换,
             * 然后 > 区域左扩, left 不加1, left不变。
             */
        else if (arr[left] > pivot) {
            std::swap( arr[--more], arr[left] );
        }
            /*
             * 如果当前位置的元素值 == 划分值,
             * 此时 left 加 1。
             */
        else {
            left++;
        }
    }

    std::swap( arr[more], arr[right] );
    return std::vector<int>{less + 1, more};
}


/*
 * 将 arr[left, right] 排好序。
 */
static void quickSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        /*
         * 第一步: 随机选一个位置, 将这个位置的值作为划分值,
         * 并且将这个位置的值与最后一个位置的值交换。
         */
        std::swap( arr[randomNumberFromTheRange( left, right )], arr[right] );

        /*
         * 然后在 [left, right], 那刚刚随机选出来的数即 arr[right] 做划分。
         * 返回的这个数组长度一定为 2, 它是要排序的序列中等于划分值区域的范围: 划分值区域的左边界和右边界。
         *
         * 因为每一次划分都会搞定一批等于划分值的元素的顺序。
         *
         * 这个返回值为数组, 数组中的两个元素,
         * 分别存储了这个等于划分值的区域的左边界位置(即左边界索引下标)
         * 和右边界位置(即右边界索引下标)。
         *
         * 每一次调用这个函数都会搞定一批等于划分值的元素的顺序。
         */
        std::vector<int> partitionRange = partition( arr, left, right );

        // 在左侧递归划分。
        quickSort( arr, left, partitionRange[0] - 1 );
        // 在右侧递归划分。
        quickSort( arr, partitionRange[1] + 1, right );
    } else {
        return;
    }
}


static void quickSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    quickSort( arr, 0, arr.size() - 1 );
}


int main(int argc, char** argv) {
    std::vector<int> arr;
    arr.reserve( 10 );
    for (int i = 0; i < 10; ++i) {
        arr.push_back( randomNumberFromTheRange( 0, 100 ));
    }
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;


    quickSort( arr );
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;


    return 0;
}
